package zijie;

/**
 * 31. 下一个排列
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 */
public class NextPermutation_31_15 {
    /**
     * 从后往前找，找到第一个下降的位置，记为 k。注意k 以后的位置是降序的。 在样例中就是找到 3
     *
     * 从 k 往后找，找到最小的比 k 要大的数。 找到 4
     *
     * 将两者交换。注意此时 k 以后的位置仍然是降序的。
     *
     * 直接将 k 以后的部分翻转（变为升序）。
     * [1,3,5,4,1]
     */
    public void nextPermutation(int[] nums){
        if(nums.length == 0){
            return;
        }
        int k = nums.length - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]){
            k--;
        }
        if(k == 0){
            reverse(nums,0,nums.length - 1);
        }else{
            int u = k;
            while (u + 1< nums.length && nums[k - 1] < nums[u + 1]) u++;
            swap(nums,k - 1,u);
            reverse(nums, k ,nums.length - 1);
        }
    }

    public void reverse(int[] nums, int a,int b){
        int l = a;
        int r = b;
        while (l < r){
            swap(nums,l,r);
            l++;
            r--;
        }
    }
    public void swap(int[] nums,int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public void nextPermutation2(int[] nums){
        if(nums.length == 0){
            return;
        }
        int k = nums.length - 1;
        while ( k - 1 >= 0 && nums[k] <= nums[k - 1]){
            k--;
        }
        if(k == 0){
            reverse2(nums,0,nums.length - 1);
        }
        int u = k;
        while (u < nums.length && nums[k - 1] < nums[u]) u++;
        swap2(nums,k-1,u);
        reverse2(nums,k,nums.length - 1);
    }

    public void reverse2(int[] nums,int l,int r){
        if(nums.length < 2) {
            return;
        }
        while (l < r){
            swap2(nums,l,r);
            l++;
            r--;
        }
    }

    public void swap2(int[] nums,int l,int r){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }








    public static void main(String[] args) {
        int[] test = {1,2,3,4,5,6};
        NextPermutation_31_15 nextPermutation_3115 = new NextPermutation_31_15();
        nextPermutation_3115.nextPermutation(test);


    }
}
